package sort;

import com.sun.corba.se.impl.orbutil.ObjectStreamClassUtil_1_3;

import java.util.Arrays;

public class Sort1 {

    public static void main(String[] args) {
        int[] nums = new int[]{111, 3, 445, 23, 6, 58, 99, 7};
        bubbleSort(nums.clone());
        selectionSort(nums.clone());
        insertionSort(nums.clone());
        shellSort(nums.clone());
        quirkSort(nums.clone());
        mergeSort(nums.clone());
        heapSort(nums.clone());
    }

    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    //冒泡排序
    //经过k轮排序
    //将第i小的数冒泡到Array[i]上
    //稳定的排序算法
    //时间复杂度  平均O(N^2)  最坏O(N^2) 最好O(n)
    //第一轮已经发现整体有序
    private static void bubbleSort(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (nums[i] > nums[j])
                    swap(nums, i, j);
            }
        }
        System.out.println("bubbleSort" + Arrays.toString(nums));
    }

    //选择排序
    //将第i小的数放在Array[i]上
    //不稳定的排序算法
    //时间复杂度  平均O(N^2)  最坏O(N^2) 最好O(N^2)
    private static void selectionSort(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int minIndex = i;
            for (int j = i; j < n; j++) {
                if (nums[minIndex] > nums[j])
                    minIndex = j;
            }
            swap(nums, i, minIndex);
        }
        System.out.println("selectionSort" + Arrays.toString(nums));
    }

    //插入排序
    //构建一个相对有序的数组，每次向前排序插入
    //稳定的排序算法
    //时间复杂度  平均O(N^2)  最坏O(N^2) 最好O(n)
    private static void insertionSort(int[] nums) {
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            int j = i - 1;
            while (j >= 0 && num < nums[j]) {
                nums[j + 1] = nums[j];
                j--;
            }
            nums[j + 1] = num;
        }
        System.out.println("insertionSort" + Arrays.toString(nums));
    }

    //希尔排序
    //类似插入排序，不过gap从length/2会慢慢减少到1
    //不稳定的排序算法
    //O(n^1.3) O(n^2) O(n)
    private static void shellSort(int[] nums) {
        int n = nums.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int num = nums[i];
                int j = i - gap;
                while (j >= 0 && nums[j] > num) {
                    nums[j + gap] = nums[j];
                    j -= gap;
                }
                nums[j + gap] = num;
            }
        }
        System.out.println("shellSort" + Arrays.toString(nums));
    }

    //快速排序
    //每次选数组第一个元素为基准
    //将数组切分成比基准小的数组 基准大的数组
    //合并当前数组
    //O(nlong^n) O(n^2) O(nlong^n)

    //为什么快排时间复杂度最坏是o(n^2)
    //假设当前已经有序
    //C(n) = (n-1) + (n-2) + ... + 1 = n(n-1)/2
    private static void quirkSort(int[] nums) {
        quirkSortHelper(nums, 0, nums.length - 1);
        System.out.println("quirkSort" + Arrays.toString(nums));
    }

    //返回分区下标
    private static void quirkSortHelper(int[] nums, int left, int right) {
        if (left > right)
            return;
        int base = nums[left];
        int i = left, j = right;
        while (i != j) {
            while (nums[j] >= base && i < j)
                j--;
            while (nums[i] <= base && i < j)
                i++;
            swap(nums, i, j);
        }
        swap(nums, i, left);
        quirkSortHelper(nums, left, i - 1);
        quirkSortHelper(nums, i + 1, right);
    }

    //归并排序
    //将数组划分成有序的子数组，再拼接子数组
    //O(nlong^n) O(nlong^n) O(nlong^n)
    private static void mergeSort(int[] nums) {
        System.out.println("mergeSort" + Arrays.toString(mergeSortHelper(nums)));
    }

    private static int[] mergeSortHelper(int[] nums) {
        int n = nums.length;
        if (n <= 1)
            return nums;
        int mid = n / 2;
        int[] left = Arrays.copyOfRange(nums, 0, mid);
        int[] right = Arrays.copyOfRange(nums, mid, n);
        return merge(mergeSortHelper(left), mergeSortHelper(right), n);
    }

    private static int[] merge(int[] nums1, int[] nums2, int n) {
        int[] result = new int[n];
        int nums1Length = nums1.length;
        int nums2Length = nums2.length;
        int resultIndex = 0, nums1Index = 0, nums2Index = 0;
        while (nums1Index < nums1Length && nums2Index < nums2Length) {
            if (nums1[nums1Index] < nums2[nums2Index])
                result[resultIndex++] = nums1[nums1Index++];
            else
                result[resultIndex++] = nums2[nums2Index++];
        }
        while (nums1Index < nums1Length) {
            result[resultIndex++] = nums1[nums1Index++];
        }
        while (nums2Index < nums2Length) {
            result[resultIndex++] = nums2[nums2Index++];
        }
        return result;
    }

    // 堆排序
    // 大顶堆/小顶堆
    // 当前节点大于左右子树  当前阶段小于左右子树
    // 升序构建大顶堆 大顶堆与末尾元素交换 重新构建堆
    private static void heapSort(int[] nums) {
        int length = nums.length;
        //初始化根堆 遍历非叶子节点
        for (int i = (length - 1) / 2; i >= 0; i--) {
            adjustHeap(nums, i, length);
        }

        for (int i = length - 1; i > 0; i--) {
            // 将最大根放入数组
            swap(nums, 0, i);
            adjustHeap(nums, 0, i);
        }
        System.out.println("heapSort" + Arrays.toString(mergeSortHelper(nums)));
    }

    //调整根堆
    private static void adjustHeap(int[] arr, int parent, int length) {
        //左子节点
        int leftNode = 2 * parent + 1;
        //右子节点
        int rightNode = 2 * parent + 2;

        int maxIndex = parent;
        if (leftNode < length && arr[leftNode] > arr[maxIndex])
            maxIndex = leftNode;
        if (rightNode < length && arr[rightNode] > arr[maxIndex])
            maxIndex = rightNode;
        if (maxIndex != parent) {
            swap(arr, parent, maxIndex);
            adjustHeap(arr, maxIndex, length);
        }

//        //父节点
//        int temp = arr[parent];
//        //左孩子 parent  = 0 lChild = 1  parent = 1 lChild = 3
//        int lChild = 2 * parent + 1;
//
//        while (lChild < length) {
//            int rChild = lChild + 1;
//            if (rChild < length && arr[lChild] < arr[rChild]) {
//                lChild++;
//            }
//
//            if (temp >= arr[lChild]) {
//                break;
//            }
//
//            arr[parent] = arr[lChild];
//            parent = lChild;
//            lChild = 2 * lChild + 1;
//            System.out.println(Arrays.toString(arr));
//        }
    }
}
